﻿You have to be careful of a vehicle’s height clearance limit on routes when you drive a truck or you could cause damage to the vehicle and property. 
Today, Mr. Shin has to load products from our company onto a truck by himself and deliver them to various retailers. 
From the company to each retailer, there are the numbers from 1 to N for the regions with height clearance limits, which vary depending on the region. 
Therefore, the height clearance limit of the route should be equal to or higher to that of the truck in order for it to pass through safely. 
That is, to pass from i to j, the minimum height clearance in those regions should be equal to or higher than that of the truck.


Mr. Shin wants to know “How high the truck should be to be able pass from i to j?” You should answer for him for each section.


Time limit: 1 second (Java: 2 seconds)


Input format


There can be more than one test case in the input file. The first line has T, the number of test cases. 
Then the totally T test cases are provided in the following lines (T ≤ 10 )
N, the number of the region with its height clearance, and Q, the number of questions, are given in order on each first line of each test case. (1 ≤ N, Q ≤ 25,000)
From the next line through to the lines of N, height clearances from 1 to N are given in order. (1 ≤ the room’s width ≤ 1,000,000,000)
From the next line through Q, the question I and J are given, which asks for the maximum height of the truck for passing from i to j.


Output format


Generate each answer on each line for each question.
Classify the test cases by generating an empty line of output at the end of each test case.


Example of Input


2
10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10
1 1
67740881
1 1


Example of Output


5
38
20
5


67740881


// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 

import java.util.Scanner;
import java.io.FileInputStream;

class Algorithm {
	public static void main(String args[]) throws Exception	{
		Scanner sc = new Scanner(System.in);
		//sc = new Scanner(new FileInputStream("input.txt"));

		int T = sc.nextInt();
		for(int tc = 0; tc < T; tc++) {

			/**********************************
			*  Implement your algorithm here. *
			***********************************/
			
			// Print the answer to standard output(screen).

		}
	}
}
